/*
 * main.cpp
 *
 *  Created on: Jun 3, 2011
 *      Author: timothy
 */

#include <omp.h>
#include <vector>
#include <list>
#include <time.h>

using namespace::std;

#include "init.h"
#include "loadgraph.h"
#include "shingletypes.h"
#include "shinglehashtable.h"
#include "unionfind.h"
#include "output.h"
#include "list.h"

#include "debug.h"

ShingleContext *g_ShingleContext;
arg_vars *g_ArgVars;

double allocTimes[MAX_THREADS_DEBUG];
int numAllocs[MAX_THREADS_DEBUG];


int main(int argc, char **argv)
{
	for(int i = 0; i < 64; ++i)
	{
		allocTimes[i] = 0;
		numAllocs[i] = 0;
	}

	// Initialize
	g_ArgVars = (arg_vars*)malloc(sizeof(arg_vars));
	*g_ArgVars = init_args(argc, argv);
	g_ShingleContext = new ShingleContext();
	ShingleHashtableEntry::SetupAllocs();
	NeighborListEntry::SetupAllocs();
	int numVertices;

	// Open the input file.
	InFile *In = new InFile();
	numVertices = In->numVertices;

	time_t wtime = time(NULL);
	// Load the graph
	Vertex *graph = (Vertex*)calloc(In->numVertices, sizeof(Vertex));
	{ // SCOPE
		int i = 0;
		char *line = (char*)malloc(In->lineLength);
		while(In->ReadLine(line))
		{
			graph[i].InitVertex(line);
			if(graph[i].ID != i)
			{
				int id = graph[i].ID;
				printf("Vertex %d not in graph!\n", i);
				memcpy(&graph[id], &graph[i], sizeof(Vertex));
				graph[i].Neighbors = 0;
				while(i < id)
				{
					graph[i++].ID = -1;
					graph[i].Neighbors = 0;
				}
			}
			++i;
		}
		free (line);
		if(i != In->numVertices)
		{
			printf("Vertex count mismatch. %d to %d\n", In->numVertices, i);
			while(i < In->numVertices)
			{
				graph[i++].ID = -1;
				graph[i].Neighbors = 0;
			}
		}
	} // END SCOPE

#ifdef REPAIR_GRAPH
	int edgeCount = In->numEdges;
	In->numEdges = 0;
	for(int i = 0; i < In->numVertices; ++i)
	{
		if(graph[i].ID >= 0)
			In->numEdges += graph[i].Repair(graph);
	}
	fflush(stdout);
	In->numEdges /= 2;
	if (edgeCount != In->numEdges)
		printf("Edge count mismatch. %d to %d\n", In->numEdges, edgeCount);
	fflush(stdout);
	FILE *output = fopen(g_ArgVars->outfile_n, "w");
	fprintf(output, "%d,%d\n", In->numVertices, In->numEdges);
	for(int i = 0; i < In->numVertices; ++i)
	{
		graph[i].ID = i;
		graph[i].WriteGEL(output);
	}
	fflush(output);
	fclose(output);

	printf("Graph repaired and saved.\n");
	return 0;
#endif
	printf("File input construction complete.\n");
	pdprint(PDPRINT_TIME, "File input finished in %ld.\n", time(NULL) - wtime);
	wtime = time(NULL);
	// Prune it
	// Create first-level shingles
	ShingleHashtable *firstShingleTable = new ShingleHashtable(In->numVertices);
//	double t1 = omp_get_wtime();
#ifndef PARALLEL_ON_TRIALS
#pragma omp parallel default(shared) // The following lines will execute in parallel with all externals shared.
#endif
	{
#ifdef ACCUMULATE_SHINGLES
		double timeGen; double timeIns; double timeNow; double timeWait;
		timeNow = omp_get_wtime();
		timeGen = timeIns = timeWait = 0.0;
		int listCount = 0;
		ShingleList *toInsert = new ShingleList();
#endif
		int vertexIndex;
		int verticesProcessed = 0;
#pragma omp for schedule(dynamic, 64)
		for(vertexIndex = 0; vertexIndex < In->numVertices; ++vertexIndex)
		{
			++verticesProcessed;
			Vertex *v = &graph[vertexIndex];
			//pdprint(PDPRINT_FILEIN, "line: %s", line);
			if(v->Neighbors->size > g_ArgVars->shingle_length)
			{
				int i;
#ifdef PARALLEL_ON_TRIALS
#pragma omp parallel for private(i) default(shared) schedule(dynamic,4)
#endif
				for(i = 0; i < g_ArgVars->num_trials; i+=4)
				{
#ifndef ACCUMULATE_SHINGLES
					firstShingleTable->Insert(v, i);
					firstShingleTable->Insert(v, i+1);
					firstShingleTable->Insert(v, i+2);
					firstShingleTable->Insert(v, i+3);
				}
			}
		}
#else // ACCUMULATE_SHINGLES
					Shingle *ins = v->MakeShingle(i, 0);
					toInsert->Push(ins);
				}
				timeGen += (omp_get_wtime() - timeNow);
				timeNow = omp_get_wtime();
				++listCount;
				if(listCount > ACCUMULATE_SHINGLES && omp_test_lock(&firstShingleTable->table_lock))
				{
					pdprint(PDPRINT_THREADING, "Offloading %d shingles.\n", toInsert->Size());
					while(toInsert->Size())
					{
						Shingle *ins = toInsert->Pop();
						firstShingleTable->InnerInsert(ins);
					}
					omp_unset_lock(&firstShingleTable->table_lock);
					timeIns += (omp_get_wtime() - timeNow);
					timeNow = omp_get_wtime();
					listCount = 0;
				}
			}
		}
		timeGen += (omp_get_wtime() - timeNow);
		timeNow = omp_get_wtime();
		pdprint(PDPRINT_THREADING, "Finished generating shingles.\n");
		if(toInsert->Size())
		{
			omp_set_lock(&firstShingleTable->table_lock);
			timeWait += (omp_get_wtime() - timeNow);
			timeNow = omp_get_wtime();
			pdprint(PDPRINT_THREADING, "Offloading %d shingles.\n", toInsert->Size());
			while(toInsert->Size())
			{
				Shingle *ins = toInsert->Pop();
				firstShingleTable->InnerInsert(ins);
			}
			omp_unset_lock(&firstShingleTable->table_lock);
			timeIns += (omp_get_wtime() - timeNow);
			timeNow = omp_get_wtime();
		}
		pdprint(PDPRINT_TIME, "Times:\n Generation: %lf\n Insertion: %lf\n Waiting: %lf\n", timeGen, timeIns, timeWait);
		pdprint(PDPRINT_DIAGNOSTICS, "%d vertices processed.\n", verticesProcessed);
#endif
		pdprint(PDPRINT_THREADING, "Finished with t1.\n");
#ifndef IGNORE_SMALL_TIMES
		int proc = omp_get_thread_num();
		pdprint(PDPRINT_TIME, "Chktime: %lf     Gentime: %lf     Alloctime: %lf [%8d]     Lsttime: %lf     Instime: %lf\n", firstShingleTable->chkTimes[proc], firstShingleTable->genTimes[proc] - allocTimes[proc], allocTimes[proc], numAllocs[proc], firstShingleTable->lstTimes[proc], firstShingleTable->insTimes[proc]);
		pdprint(PDPRINT_TIME, "Locked time: %lf     Locking time: %lf    %8d collisions in %9d locks.\n", firstShingleTable->lockedTimes[proc], firstShingleTable->lockingTimes[proc], firstShingleTable->collisions[proc], firstShingleTable->timesLocked[proc]);
#endif

	}
//	t1 = omp_get_wtime() - t1;
	printf("First shingle construction complete.\n");
//	pdprint(PDPRINT_TIME, "Unindexed time: %lf.\n", t1 - firstShingleTable->chkTimes[0] - firstShingleTable->genTimes[0] - firstShingleTable->insTimes[0]);
	pdprint(PDPRINT_SHINGLE_2, "Table 1 shingle count: %d\n", firstShingleTable->Count());
	pdprint(PDPRINT_DIAGNOSTICS, "Table 1 is %6f%% full.\n", ((double)firstShingleTable->Count()/firstShingleTable->Size)*100);
	pdprint(PDPRINT_TIME, "Table 1 finished in %ld.\n", time(NULL) - wtime);
	wtime = time(NULL);

	free(graph);
//	getc(stdin);

	// Close the input file
	delete(In);

	// Create second level shingles
	// Do union-find
	UnionFindTree *Union = new UnionFindTree(numVertices);
	firstShingleTable->InitIterator();
#ifndef PARALLEL_ON_TRIALS
#pragma omp parallel default(shared) // Once again, parallel with all externals shared
#endif
	{
		Shingle *next = 0;
		int proc = omp_get_thread_num();
		do {
			next = firstShingleTable->Iterate();
			if(next == NULL) break;
			if(next->neighborCount < g_ArgVars->shingle_length)
			{
				Union->numCulledInserts[proc] += g_ArgVars->num_trials;
				continue;
			}
			int i;
#ifdef PARALLEL_ON_TRIALS
#pragma omp parallel for private(i) default(shared) schedule(dynamic,2)
#endif
			for(i = 0; i < g_ArgVars->num_trials; i+=4)
			{
				Union->Insert(next, i+0);
				Union->Insert(next, i+1);
				Union->Insert(next, i+2);
				Union->Insert(next, i+3);
			}
		} while(next != NULL);
		pdprint(PDPRINT_THREADING, "Finished with t2.\n");
	}

	fflush(stderr);
	printf("Union find complete.\n");
	pdprint(PDPRINT_TIME, "Union finished in %ld.\n", time(NULL) - wtime);
	for(int i = 1; i < omp_get_max_threads(); ++i)
	{
		Union->numCulledInserts[0] += Union->numCulledInserts[i];
		Union->numUnculledInserts[0] += Union->numUnculledInserts[i];
	}
	Union->numCulledInserts[0] /= g_ArgVars->num_trials;
	Union->numUnculledInserts[0] /= g_ArgVars->num_trials;
	pdprint(PDPRINT_DIAGNOSTICS, "Inserts: %ld culled and %ld unculled.\n", Union->numCulledInserts[0], Union->numUnculledInserts[0]);
	wtime = time(NULL);
	fflush(stderr);

	// Output
	// Output is done in serial.
	In = new InFile(); // Re-open the input file to get original edge/vertex information.
	OutFile *Out = new OutFile(In, Union);
	Out->Write();

	pdprint(PDPRINT_DIAGNOSTICS, "Number of communities: %ld.\n", Union->GetNumberOfGroups());
	pdprint(PDPRINT_DIAGNOSTICS, "Number of singletons:  %ld.\n", Union->GetNumberOfSingletons());
	Union->AuditGroupSizes();
	Union->AuditEdges();
	fflush(stderr);
	printf("Outfile complete. Terminating.\n");
	delete(Out);
	delete(In);
	delete(Union);
	delete(firstShingleTable);
	delete(g_ShingleContext);
	free(g_ArgVars);
}
